import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;



public class MCMC {
	double matrix[][]; // the transitive matrix, which is the output of the training data
	double marginals[];
	HashMap<String, Integer> indices;
	ArrayList<String> unPuncInput;	//takes an input string from 
	ArrayList<String> inputOriginal;
	ArrayList<String> inputStringP;
	ArrayList<String> inputStringUP;
	int executions;
	int totalRuns;
	ArrayList<String> outString;
	int perturbFactor;
	ArrayList<String> bestSolution;
	ArrayList<String> toCompare;
	String inFile;
	int[][] outputAnalysis;
	boolean outputAnalysisFlag;
	long startTime, endTime;
	
	public MCMC(double MC[][], double MarginalProbs[], String inputFile, HashMap<String, Integer> inputIndices, 
			 int execution, int runs, int pFactor) throws IOException
	{
		startTime = System.currentTimeMillis();
		matrix = MC;
		marginals = MarginalProbs;
		indices = inputIndices;
		executions = execution;
		perturbFactor = pFactor;
		totalRuns = runs;
		inFile = inputFile;
		outputAnalysisFlag = false;
		processInputFile(inputFile);
	}
	
	public void setOutputAnalysis()
	{
		outputAnalysisFlag = true;
		if(outputAnalysisFlag)
			outputAnalysis = new int[totalRuns][executions/2];
	}
	public void produceOutput() throws IOException
	{
		endTime = System.currentTimeMillis();
		String outputFile = inFile + "_punc.out.txt";
		FileWriter fw = new FileWriter(outputFile);
		BufferedWriter bw = new BufferedWriter(fw); 
		bw.write("Total execution time: " + (endTime - this.startTime)/1000.0 + " seconds. \n\n");
		
		bw.write("Original text: \n");
//		this.printSolution(inputOriginal);
		
		for(int i = 0; i < inputOriginal.size(); i++)
		{
			bw.write(inputOriginal.get(i)+ " ");
		}
		
		bw.write("\n");
		
		bw.write("Processed text (tags): \n");
		
		for(int i = 0; i < bestSolution.size(); i++)
		{
			if(!bestSolution.get(i).equals(""))
				bw.write(bestSolution.get(i)+ " ");
			
		}
		this.printSolution(this.bestSolution);
		bw.write("\n\n");
		
		bw.write("Processed text: \n");
		
		for(int i = 0; i < inputStringUP.size(); i++)
		{
			if(i % 2 == 0)
				bw.write(inputStringUP.get(i));
			else
			{
				if(!bestSolution.get(i).equals(""))
					bw.write(" " + bestSolution.get(i) + " ");
				else
					bw.write(bestSolution.get(i));
			}
		}
		
		bw.write("\n");
		
		bw.close();
		if(outputAnalysisFlag)
		{
			outputFile = inFile + "_outAnalysis.out.txt";
			fw = new FileWriter(outputFile);
			bw = new BufferedWriter(fw); 
			String line = "";
			for(int i = 0; i < executions/2; i++)
				line = line + "\t" + i;
			bw.write(line + "\n");
			
			//write the matrix out now
			for(int i = 0; i < this.totalRuns; i++)
			{
				line = Integer.toString(i);
				for(int j = 0; j < executions/2; j++)
					line = line + "\t" + this.outputAnalysis[i][j];
				bw.write(line + "\n");
			}
			bw.close();
		}
		
	}
	
	private void processInputFile(String inputFile) throws IOException
	{
		inputOriginal = new ArrayList<String>();
		inputStringP = new ArrayList<String>();
		unPuncInput = new ArrayList<String>();
		inputStringUP = new ArrayList<String>();
		ArrayList<String> inputStringUPTemp = new ArrayList<String>();
		FileReader fr = new FileReader(inputFile);
		BufferedReader br = new BufferedReader(fr);
		String s, s2;
		Pattern r = Pattern.compile(Driver.pattern);
		
		while((s = br.readLine()) != null) 
		{
			Matcher m = r.matcher(s);

			while (m.find( )) 
			{
				inputStringP.add(m.group(1));
				inputOriginal.add(m.group(3));
				//tag = m.group(3);
			}
		}
		
		this.printSolution(inputOriginal);
		toCompare = new ArrayList<String>();
		
		//strip the punctuations off
		for(int i = 0; i < inputOriginal.size(); i++)
		{
			s = inputOriginal.get(i);
			if(s.matches(Driver.eosPatten))
			{
				inputOriginal.set(i, "e");
			}
			else if(s.matches(Driver.pausePatten))
			{
				inputOriginal.set(i, "p");
			}
			else
			{
				unPuncInput.add(s);
				inputStringUPTemp.add(inputStringP.get(i));
			}
		}
		
		//The input string without punctuations
		resizeArray(inputStringUP, inputStringUPTemp.size() * 2);
		int count = 0;
		int count2 = 0;

		while(count < inputStringUPTemp.size())
		{
			inputStringUP.set(count2, inputStringUPTemp.get(count));
			count++;
			count2 = count2 + 2;
		}
		
//		System.out.println(unPuncInput.size());
//		this.printSolution(unPuncInput);
		//the following is for output analysis
		//once the simulation is done, we can worry then
		boolean hadTag = true;
		
		s = inputOriginal.get(0);
		toCompare.add(s);
		for(int i = 1; i < inputOriginal.size(); i++)
		{
			s = inputOriginal.get(i);
			
			if(s.matches("e"))
			{
//				toCompare.add(s);
				hadTag = false;
				toCompare.add("e");
			}
			else if(s.matches("p"))
			{
//				toCompare.add(s);
				toCompare.add("p");
				hadTag = false;
			}
			else
			{
				if(hadTag)
					toCompare.add("");
				toCompare.add(s);
				
				hadTag = true;
			}
		}
		
//		System.out.println(toCompare.size());
//		this.printSolution(toCompare);
		System.out.println("Initial solution likelihood " + this.evaluateSolution(toCompare));
	}
	
	private void resizeArray(ArrayList<String> input, int size)
	{
		for(int i = 0; i < size; i++)
			input.add("");
	}
	
	private ArrayList<String> generateInitialInput(ArrayList<String> input)
	{
		//the initial input is without any punctuation or eos markers.
		//we could put the marks using the MC or randomly
		int size = input.size();
		ArrayList<String> output = new ArrayList<String>(size);
		resizeArray(output, size * 2);
		int count = 0;
		int count2 = 0;

		while(count < size)
		{
			output.set(count2, input.get(count));
			count++;
			count2 = count2 + 2;
		}
		
		perturbSolutionSmall(output, perturbFactor);
		return output;
	}
	
	double evaluateSolution(ArrayList<String> solution)
	{
		double score = 0.0;
		int count = 1, index2 = 0;
		int index = 0; 
		score = marginals[index];
//		score = 1.0;
//		System.out.println();
		
		while(count < solution.size())
		{
//			System.out.print(" index " + index + " index2 " + index2);
			index2 = indices.get(solution.get(count++));
			if(matrix[index][index2] == 0.0)
			{
//				System.out.println(" count - 2 " + (count - 2) + " count - 1 " + (count - 1) );
//				System.out.println(" string index " + solution.get(count - 2) + " string index2 " + solution.get(count - 1) );
//				System.out.println(" index " + index + " index2 " + index2);
//				this.printSolution(solution);
				return 0.0;
			}
			score = score * matrix[index][index2];
			index = index2;
		}
		
//		System.out.println();
		
		return score;
	}
	
	private void perturbSolutionSmall(ArrayList<String> solution, int totalPlaces)
	{
		//just find the totalPlaces places to perturb
		//since every odd space is a potential target
		//for a punctuation, eos, or a null
		int index = 1;
		double prob, prob2;
		Random rand = new Random(1234567823);
		Random rand2 = new Random(987654312);
		Random rand3 = new Random(2132132132);
		double threshold = .1; //for perturbation
		double putPunc = .50; //for punctuation
		HashSet<Integer> visited = new HashSet<Integer>();
		
		int count = 0;
		
		while(count < totalPlaces)
		{
			index = rand.nextInt(solution.size());
			
			while(visited.contains(index))
				index = rand.nextInt(solution.size());
			visited.add(index);
			
			if(index % 2 == 0)
			{
				if(index == solution.size() - 1)
					index--;
				else
					index++;
			}
			
			prob = rand3.nextDouble();
			
			if(prob >= threshold) //decide whether to put pause/eos
			{
				//perturb this place
				prob2 = rand2.nextDouble();
				
				if(prob2 <= putPunc)
				{
					solution.set(index, "p");
				}
				else
					solution.set(index, "e");
			}
			else
				solution.set(index,"");	
			
			count++;
		}
	}
	
	
	private void perturbSolutionLarge(ArrayList<String> solution)
	{
		//since every odd space is a potential target
		//for a punctuation, eos, or a null
		int index = 1;
		double prob, prob2;
		Random rand = new Random();
		Random rand2 = new Random();
		double threshold = .9; //for perturbation
		double putPunc = .75; //for punctuation
		while(index < solution.size())
		{
			prob = rand.nextDouble();
			
			if(prob >= threshold) //decide whether to put pause/eos
			{
				//perturb this place
				prob2 = rand2.nextDouble();
				
				if(prob2 <= putPunc)
				{
					solution.set(index, "p");
				}
				else
					solution.set(index, "e");
			}
			else
				solution.set(index,"");	//else just put null
			index = index + 2;
		}
	}

	public void MonteCarloMC()
	{
		bestSolution = new ArrayList<String>();
		
		ArrayList<String> aSolution = generateInitialInput(unPuncInput);
		ArrayList<String> newSolution = new ArrayList<String>();
//		ArrayList<String> bestSolutionRun = new ArrayList<String>(); //the best solution found by run
		Random rand= new Random(234324234);
		int acceptCount = 0;
		double bestSolutionRunValue = 0.0;
		perturbSolutionSmall(aSolution, perturbFactor);
		double eval = evaluateSolution(aSolution);
		double bestValue = eval;
		
//		if(outputAnalysisFlag)
//		{
//			resizeArray(bestSolutionRun, aSolution.size());
//			copyArray(aSolution, bestSolutionRun);
//			bestSolutionRunValue = eval;
//		}
		double eval2, acceptRate, prob;
		resizeArray(bestSolution, aSolution.size());
		resizeArray(newSolution, aSolution.size());
		
		copyArray(aSolution, bestSolution);
		copyArray(aSolution, newSolution);
		
		for(int k = 0; k < totalRuns; k++)
		{
			acceptCount = 0;
			bestSolutionRunValue = 0.0;
			
			for(int i = 0; i < executions; i++)
			{
//				printSolution(aSolution);
				perturbSolutionSmall(aSolution, perturbFactor);
//				printSolution(aSolution);
//				printSolution(bestSolution);
				
				eval2 = evaluateSolution(aSolution);
//				if(eval2 == 0.0)
//					return;
//				System.out.println("eval2 " + eval2);
				acceptRate = Math.min(1.0, (eval2 / eval));
				prob = rand.nextDouble();
				
				if(prob < acceptRate) //then accept the solution
				{
					copyArray(aSolution, newSolution);
						acceptCount++;
					if(eval2 > bestValue)
					{
						copyArray(newSolution, bestSolution);
						System.out.println("best solution found ");
						bestValue = eval2;
					}
					
//					if(outputAnalysisFlag)
//					{
//						if(eval2 > bestSolutionRunValue)
//						{
//							copyArray(aSolution, bestSolutionRun);
//							bestSolutionRunValue = eval2;
//						}
//					}
				}
				else
					copyArray(newSolution, aSolution);
				
				if(outputAnalysisFlag && i >= executions/2)
				{
					int distance = distanceBetwSolutions(aSolution, this.toCompare);
					outputAnalysis[k][i - executions/2] = distance;
				}
			}
			
			//creating a new solution
			aSolution = generateInitialInput(unPuncInput);
			
//			if(outputAnalysisFlag)
//			{				
//				//resetting the best solution of a run
//				copyArray(aSolution, bestSolutionRun);
//				bestSolutionRunValue = eval;
//			}
			
			System.out.println("Finished run " + (k + 1));
			System.out.println("Best likelihood " + bestValue + " acceptCount " + acceptCount);
//			printSolution(inputOriginal);
//			System.out.println(unPuncInput);
		}
	}

	private int distanceBetwSolutions(ArrayList<String> solution1, ArrayList<String> solution2)
	{
		int distance = 0;
		String s1, s2;
		for(int i = 1; i < solution1.size(); i = i + 2)	
		{
			s1 = solution1.get(i).trim();
			s2 = solution2.get(i).trim();
			if(!s1.equals(s2))
			{
				distance++;
//				System.out.print(solution1.get(i) + " " + solution2.get(i) );
//				System.out.println();
			}
			
			
		}
		
		return distance;
			
	}
	
	private void printSolution(ArrayList<String> source)
	{
		for(int i = 0; i < source.size(); i++)
		{
			System.out.print(source.get(i));
			if(source.get(i).equals(""))
				System.out.print(" ");
		}
		System.out.println("\nprinted.\n");
	}
	
	private void copyArray(ArrayList<String> source, ArrayList<String> target)
	{
		for(int i = 0; i < source.size(); i++)
			target.set(i, source.get(i));
	}
}